\subsubsection{Übung (iii) - \buchmann{15.5.3}}
\paragraph{Aufgabe} 
Eine Weiterentwicklung des Fiat-Shamir-Verfahrens ist das Feige-Fiat-Shamir-Protokoll. Eine vereinfachte Version sieht so aus: Alice benutzt einen RSA-Modul $n$. Sie wählt $s_1,\dotsc,s_k$ gleichverteilt zufällig aus $\{1,\dotsc,n-1\}$ und berechnet $v_i = s^2_i\mod{n}, 1\leq i \leq k$. Ihr öffentlicher Schlüssel ist $(n,v_1,\dotsc,v_k)$. Ihr geheimer Schlüssel ist $(s_1,\dotsc,s_k)$. Um Bob von ihrer Identität zu überzeugen, wählt Alice $r\in \{1,\dotsc,n-1\}$ zufällig, berechnet $x = r^2\mod{n}$ und schickt $x$ an Bob. Bob wählt gleichverteilt zufällig $(e_1,\dotsc,e_k)\in \{0,1\}^k$ und schickt diesen Vektor an Alice (Challenge). Alice schickt $y = r\prod^k_{i=1} s^{e_i}_i$ an Bob (Response). Bob verifiziert $y^2 = x\prod^k_{i=1} v^{e_i}_i\mod{p}$. Mit welcher Wahrscheinlichkeit kann ein Betrüger in einem Durchgang dieses Protokolls betrügen?

\paragraph{Lösung}
Würde ein Betrüger versuchen, sich zu Identifizieren, ohne Kenntnis vom geheimen Schlüssel $(s_1,\dotsc,s_k)$ zu haben, müsste er $x$ aus einem festen $y$ berechnen: 
$$y^2\equiv x\prod\limits_{i=1}^{k} v_i^{e_i}\mod{n}$$ 
$$y^2\prod\limits_{i=1}^{k} v_i^{-e_i}\equiv x\mod{n}$$
Ein Betrüger kann also nur für einen Vektor $(e_1,\dotsc,e_k)$ die Quadratwurzel aus $x\prod\limits_{i=1}^{k} v_i^{e_i}\mod{n}$ kennen. 

Die Wahrscheinlichkeit, dass der Verifizierer als Challenge den Vektor $(e_1,\dotsc,e_k)$ des Betrügers wählt, ist also $(\frac{1}{2})^k=2^{-k}$.

